home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Stacks / Updates⁄New / TEXAS for BMUG / C progs / qndxr.2 ƒ / qndxr (for suns⁄vaxen).c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-02-11  |  50.1 KB  |  1,655 lines  |  [TEXT/ttxt]
  1.  
  2. /*    revised main indexer program 'qndxr.c' by ^z -- 870820-...
  3.  *
  4.  * revised 870930-1008 to give the user more options and control of how
  5.  * delimiters are defined and handled.  Now can choose:
  6.  *    - the default:  any non-alphanumeric characters are delimiters (my
  7.  *        original approach, and perhaps the simplest to understand and use);
  8.  *    - option "-e":  keep punctuation characters ONLY when they are embedded
  9.  *        in between non-delimiter characters, otherwise turn them into
  10.  *        delimiters (approach invented by Bill Hole of MicroDynamics Ltd.;
  11.  *        very nice for displaying 'words' such as don't, non-ASCII, 3.14159,
  12.  *        87/10/02, etc. without splitting them up and requiring proximity
  13.  *        searching);
  14.  *    - option "-a":  keep ALL punctuation characters, whether embedded in
  15.  *        words or not (best for indexing FORTH programs and such, but does
  16.  *        make spurious 'distinct' words at ends of sentences, etc.);
  17.  *    - option "-s":  keep all special (non-ASCII) characters (with values
  18.  *        in the range 128-255; in the Apple character set, these are the
  19.  *        symbols that carry umlauts, tilde, accents, etc., making this
  20.  *        option the best for foreign-language and symbol-heavy files);
  21.  *        default is to remove the special characters.
  22.  *
  23.  *    Note that option "-s" can be combined with any of the other options;
  24.  *    options "-e" and "-a" are mutually exclusive.  (Actually, "-a" in my
  25.  *    implementation overrides "-e".)  The "-e" option does require
  26.  *    peeking ahead one character before deciding on the fate of
  27.  *    a punctuation symbol, but that isn't too hard to arrange....
  28.  *
  29.  *    ---------------------------------------------------------------
  30.  *
  31.  * Synopsis of the qndxr.c program's approach to sorting an index:
  32.  *    - load a chunk of the input file into memory; during the loading,
  33.  *        filter the characters appropriately, turning lower-case
  34.  *        into capitals, changing delimiters into \0's, and noting down
  35.  *        the locations of the beginnings of keys (words) in a ptr array;
  36.  *    - do a quicksort on the ptr array, using the keys in the buffer
  37.  *        to sort on;
  38.  *    - write the resulting sorted list of pointers along with their keys
  39.  *        to disk as files, named x0k0 and x0p0, in the *.k and *.p formats
  40.  *        used in ndxr.15;
  41.  *    - repeat the above steps with another chunk of the input file, and
  42.  *        name the resulting files x0k1 and x0p1; repeat, etc., until the
  43.  *        input file is all sorted into chunks;
  44.  *    - begin to merge the sorted files in an N-way merge ... for the
  45.  *        specific case of N=2, for example, merge x0k0/x0p0 and
  46.  *        x0k1/x0p1 into x1k0/x1p0; merge x0k2/x0p2 and x0k3/x0p3 into
  47.  *        x1k1/x1p1; etc., deleting the 0th-generation files as they are
  48.  *        merged;
  49.  *    - merge x1k0/x1p0 and x1k1/x1p1 into x2k0/x2p0, etc., and continue
  50.  *        merging subsequent generations until everything has become a
  51.  *        single pair of index files, xnk0/xnp0, which is then renamed
  52.  *        to be the original document name with '.k' and '.p' endings.
  53.  *
  54.  *    ---------------------------------------------------------------
  55.  *
  56.  * Comparison with the older radix sort approach:
  57.  *    The new quicksort/mergesort method gains a bit in speed (since so
  58.  *    much of the work is done in memory rather than streaming from disk
  59.  *    back and forth) and also saves on disk space requirements (since
  60.  *    the k and p files are significantly compressed relative to the raw
  61.  *    index files formerly used during index sorting).  The old radix sort
  62.  *    tended to only achieve about 2 MB/hour indexing on my Mac Plus setup,
  63.  *    and it required 5-6 times the size of the original file in free
  64.  *    disk space during indexing.  This new approach achieves >4 MB/hour
  65.  *    in tests on the same Mac Plus, and only requires about 1.9 times
  66.  * the original file size in free space!
  67.  *
  68.  *    The new approach also allows for greater key length -- try recompiling
  69.  *    with KEY_LENGTH of 28, for instance -- without such severe disk space
  70.  *    penalties as the old radix sort would have incurred, and without severe
  71.  *    time penalties.  (Duplicate words in the chunks are only stored once
  72.  *    in the key file, though each must have an entry in the pointer file.)
  73.  *
  74.  *    The only obvious disadvantage of the quicksort/mergesort approach is
  75.  *    that it is an O(NlogN) procedure rather than O(N), and thus gets slower
  76.  *    when files get very large.  (Radix sorting is strictly linear in N,
  77.  *    in theory anyway.)
  78.  *
  79.  *    ---------------------------------------------------------------
  80.  *
  81.  *    For further details, contact the author:
  82.  *     Mark Zimmermann             science (at) NEMS.ARPA
  83.  *     9511 Gwyndale Dr.           [75066,2044] on CompuServe
  84.  *     Silver Spring, MD  20910
  85.  *     301-565-2166
  86.  *    ---------------------------------------------------------------
  87.  */
  88.  
  89. #include <stdio.h>
  90. #include <strings.h>
  91. #include <ctype.h>
  92.  
  93. /* --------------header file--------------- */
  94.  
  95. /* header file for project qndxr -- by ^z -- 870820-0913-...
  96.  */
  97.  
  98. /* tell what compiler we're using ... Lightspeed C by Think, if the
  99.  * following line is #defined ... essentially, when LIGHTSPEED is here,
  100.  * assume that we have only 16-bit int variables and that Macintosh
  101.  * toolbox traps are available ... when LIGHTSPEED is not #defined,
  102.  * assume that ints can hold more like 32 bits without error, so more
  103.  * can be done using standard I/O routines from <stdio>
  104.  */
  105. /* #define LIGHTSPEED */
  106.  
  107. /* preprocessor 'function' to turn on/off debug printing of detailed info
  108.  *    during program runs ... when debugging, use a statement:
  109.  * #define DEBUG(fmt, arg)   printf (fmt, arg)
  110.  * ... and when not debugging, just use:  #define DEBUG(fmt, arg)
  111.  * to effectively remove those print commands....
  112.  */
  113. /* #define DEBUG(fmt, arg)   printf (fmt, arg) */
  114. #define DEBUG(fmt, arg)
  115.  
  116. /* sort on KEY_LENGTH characters ... make it 28 rather arbitrarily as an
  117.  * experiment ... want it long enough to avoid truncation of legitimate
  118.  * words, but short enough to save some space in the *.k files ... an
  119.  * alternative value is 12, for compatibility with the older ndxr.c program
  120.  * and brwsr.c, if they haven't been revised to allow for longer keys....
  121.  */
  122. #define KEY_LENGTH  28
  123.  
  124. /* define a structure for the index_keys file
  125.  */
  126. typedef struct
  127.   {
  128.     char kkey[KEY_LENGTH];
  129.     long ccount;
  130.   }  KEY_REC;
  131.  
  132. /* define a structure for my simpleminded I/O buffers ...
  133.  */
  134. typedef struct
  135.   {
  136.     char *zbufbase;
  137.     char *zbufp;
  138.     long zbufcounter;
  139.     long zbufsize;
  140.     FILE *zbuffilep;
  141.     int  zbufitemsize;
  142.   }  ZBUF;
  143.  
  144. /* choose this size to be the default memory size used for total buffer
  145.  * space ... for convenience on the Mac Plus, I have picked 512 kB, which
  146.  * leaves me a bit of space to spare ....
  147.  */
  148. #define DEFAULT_MEMSIZ  524288
  149.  
  150. /* merge this many files at each stage of the merging operation for index
  151.  * building ... 2 means a binary merge, etc. ... one needs to have at least
  152.  * 5 + 2 * NMERGE I/O buffers around:  for each of NMERGE files, there is
  153.  * a *.k keys file and a *.p pointers file; plus there must be a single
  154.  * output *.k and a single output *.p file; plus there is the need for stdin,
  155.  * stdout, and stderr to be open as well.  Thus, I have found that a 4-way
  156.  * merge (NMERGE = 4) works pretty nicely....
  157.  */
  158. #define NMERGE  4
  159.  
  160. #ifndef TRUE
  161. #define TRUE  1
  162. #endif
  163.  
  164. #ifndef FALSE
  165. #define FALSE  0
  166. #endif
  167.  
  168. /* CMASK makes sure that a returned character isn't sign-extended
  169.  */
  170. #ifndef CMASK
  171. #define CMASK  0xFF
  172. #endif
  173.  
  174. /* put the prototypes for my functions here... assume that if LIGHTSPEED
  175.  * is #define'd, then we want to use prototypes....
  176.  */
  177. #ifdef LIGHTSPEED
  178.  
  179. /* in qndxr unix main.c */
  180. void punt(void);
  181. void openfile(FILE *file, char *mode);
  182. void main(void);
  183.  
  184. /* in qndxr.c */
  185. void _main(int argc, char *argv[]);
  186.  
  187. /* in bufio.c */
  188. void create_zbuffer (int n, long bufsize, FILE *buffile, int bufitemsize);
  189. void free_zbuffer (int n);
  190. char *next_input_item (int n);
  191. void load_zbuffer (int n);
  192. char *next_output_item (int n);
  193. void flush_zbuffer (int n);
  194.  
  195. /* in build_indices.c */
  196. int build_indices (void);
  197.  
  198. /* in doc_buf.c */
  199. char *make_buf (long bufsiz);
  200. long load_doc_buffer (char *doc, long doc_bufsiz, char **ptr);
  201. int filtered_getc (void);
  202.  
  203. /* in merge_files.c */
  204. void nway_merge_kpfiles (FILE *ink[], FILE *inp[], FILE *outk, FILE *outp,
  205.         int n);
  206. void copy_ptr_recs (int inzbuf, long count, int outzbuf);
  207. void copy_key_rec (char *kkey, long ccount, int outzbuf);
  208. int merge_not_finished (KEY_REC *kr[], int n);
  209. int smallest_key (KEY_REC *kr[], int n);
  210.  
  211. /* in merge_indices.c */
  212. int merge_indices (char *doc_filename);
  213.  
  214. /* in file_utils.c */
  215. void write_sorted_files (char *doc, char **ptr, long nwords,
  216.         int pass_number, long offset);
  217. int is_new_word (char *w0, char *w1);
  218. void write_new_key (char *p, char *kp);
  219.  
  220. /* in merge_utils.c */
  221. FILE *open_inkfile (int generation_number, int file_number);
  222. FILE *open_inpfile (int generation_number, int file_number);
  223. void fix_oddball_file_name (int generation_number, int file_number);
  224. void fix_final_file_names (int generation_number, char *doc_filename);
  225. FILE *open_outkfile (int generation_number, int file_number);
  226. FILE *open_outpfile (int generation_number, int file_number);
  227. void remove_used_infiles (int generation_number, int file_number, int n);
  228. void close_infiles (FILE *ink[], FILE *inp[], int n);
  229.  
  230. /* in misc_utils.c */
  231. long set_params (int argc, char *argv[]);
  232. long set_zbufsiz (long zb);
  233. void set_parser_options (char *str);
  234. void check_interrupt (void);
  235. long file_size (FILE *fp);
  236.  
  237. /* in open_files.c */
  238. FILE *open_docfile (int argc, char *argv[]);
  239. FILE *open_kfile (int pass_number);
  240. FILE *open_pfile (int pass_number);
  241.  
  242. /* in zqsort.c */
  243. void zqsort (char **first, char **last);
  244. int compare_ptrs (char **p1, char **p2);
  245. int zstrcmp (char *s1, char *s2);
  246.  
  247. #endif
  248.  
  249.  
  250. /* ----------------------main program file---------------- */
  251.  
  252.  
  253. /* define a global variable to hold the chosen size of a fundamental
  254.  * quantum of buffer space ... experiments with dynamically choosing
  255.  * it at runtime seem to cause occasional problems on the Macintosh,
  256.  * and have other risks with virtual memory systems, so default to
  257.  * DEFAULT_MEMSIZ total buffer space but let the user override with
  258.  * a command-line choice to suit ... see function set_zbufsiz() for
  259.  * further discussion....
  260.  */
  261. long zbufsiz;
  262.  
  263. /* define a global variable to tell whether or not all punctuation chars
  264.  * are kept...
  265.  */
  266. int keep_all_punct = FALSE;
  267.  
  268. /* define a global variable to tell whether or not only embedded punctuation
  269.  * characters are preserved...
  270.  */
  271. int keep_embedded_punct = FALSE;
  272.  
  273. /* define a global variable to tell whether or not to keep special,
  274.  * non-ASCII characters...
  275.  */
  276. int keep_special_chars = FALSE;
  277.  
  278. /* define a global variable to hold the (FILE *) for the document file
  279.  */
  280. FILE *doc_file;
  281.  
  282. /* main program to do the work ... 
  283.  */
  284.  
  285. void main(argc, argv)
  286.   int argc;
  287.   char *argv[];
  288.   {
  289.     unsigned long start_time, end_time, time();
  290.     long set_params(), file_size();
  291.     char *ctime();
  292.     FILE *open_docfile();
  293.  
  294.     time (&start_time);
  295.     printf ("Starting work:  %s\n", ctime (&start_time));
  296.     
  297.     printf ("\nOpening document file \"%s\"...\n", argv[1]);
  298.     doc_file = open_docfile (argc, argv);
  299.  
  300.     zbufsiz = set_params (argc, argv);
  301.     printf ("Using buffers of size %ld each...\n", zbufsiz);
  302.  
  303.     printf ("Beginning to build index...\n");
  304.     while (build_indices ());
  305.  
  306.     printf ("Beginning to merge index subfiles...\n");    
  307.     while (merge_indices (argv[1]));
  308.  
  309.     time (&end_time);
  310.     printf ("\nEnding work:  %s\n", ctime (&end_time));
  311.     printf ("Elapsed time  = %ld seconds.\n", end_time - start_time);
  312.     printf ("Indexing rate = %.2f megabytes/hour.\n", file_size (doc_file) *
  313.                   0.003600 / ( end_time - start_time ));
  314.     printf ("Input database file \"%s\" was %ld bytes long.\n", argv[1],
  315.                   file_size (doc_file));
  316.  
  317.     fclose (doc_file);
  318.   }
  319.  
  320.  
  321. /* -------------------bufio.c file------------------- */
  322.  
  323. /* This is the file 'bufio.c' ... by ^z, 870830-0913- ... it includes 
  324.  * definitions of some buffer words to accumulate information on its
  325.  * way to/from the disks ... use these to speed up operations and reduce
  326.  * disk head movements, in place of calls to fputc(), fread(), fwrite(),
  327.  * etc. ... try to make them very general so that they will simplify
  328.  * other tasks....
  329.  *
  330.  */
  331.  
  332.  
  333. /* set up some buffers here to save on disk head movement and speed up
  334.  * operations ... use my simple ZBUF structure for both input and
  335.  * output operations ... keep everything static, local here to this file
  336.  * for safety's sake ... allocate enough items here for all the buffers
  337.  * that we may need for an NMERGE-way merge operation, taking into account
  338.  * the need for input buffers for all the NMERGE *.k and *.p files plus
  339.  * the output files *.k and *.p as well....
  340.  */
  341.  
  342. static ZBUF zbuffer[2 + 2 * NMERGE];
  343.  
  344.  
  345. /* function to create a zbuffer and set its parameters appropriately
  346.  */
  347.  
  348. void create_zbuffer (n, bufsize, buffile, bufitemsize)
  349.   int n, bufitemsize;
  350.   long bufsize;
  351.   FILE *buffile;
  352.   {
  353.     char *make_buf();
  354.     
  355.     zbuffer[n].zbufbase = make_buf (bufsize);
  356.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  357.     zbuffer[n].zbufcounter = 0;
  358.     zbuffer[n].zbufsize = bufsize;
  359.     zbuffer[n].zbuffilep = buffile;
  360.     zbuffer[n].zbufitemsize = bufitemsize;
  361.   }
  362.  
  363.  
  364. /* function to free a zbuffer ...
  365.  */
  366.  
  367. void free_zbuffer (n)
  368.   int n;
  369.   {
  370.     free (zbuffer[n].zbufbase);
  371.   }
  372.  
  373.  
  374. /* function to return a pointer to the next item in a chosen input
  375.  * buffer 'n'; it reloads the buffer if necessary ... returns NULL
  376.  * pointer when there's nothing left in the file ...
  377.  */
  378.  
  379. char *next_input_item (n)
  380.   int n;
  381.   {
  382.     char *result;
  383.     void load_zbuffer();
  384.     
  385.     if (zbuffer[n].zbufcounter == 0)
  386.         load_zbuffer (n);
  387.     
  388.     zbuffer[n].zbufcounter -= zbuffer[n].zbufitemsize;
  389.     if (zbuffer[n].zbufcounter >= 0)
  390.       {
  391.         result = zbuffer[n].zbufp;
  392.         zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  393.         return (result);
  394.       }
  395.     else
  396.         return (NULL);
  397.   }
  398.  
  399.  
  400. /* function to load the nth zbuffer appropriately ... it resets the buffer
  401.  * pointers, etc. ... might as well give the user a chance to interrupt (in
  402.  * the Macintosh version) here, as long as we have to go to the disk anyway....
  403.  */
  404.  
  405. void load_zbuffer (n)
  406.   int n;
  407.   {
  408.     long nread;
  409.     void exit(), check_interrupt();
  410.  
  411. #ifdef LIGHTSPEED
  412.     nread = zbuffer[n].zbufsize;
  413.     FSRead (zbuffer[n].zbuffilep->refnum, &nread, zbuffer[n].zbufbase);
  414. #else
  415.     nread = fread (zbuffer[n].zbufbase, sizeof(char),
  416.             (int)zbuffer[n].zbufsize, zbuffer[n].zbuffilep);
  417. #endif
  418.  
  419.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  420.     zbuffer[n].zbufcounter = nread;
  421.     
  422.     if (ferror (zbuffer[n].zbuffilep))
  423.       {
  424.         printf ("\nFatal error in load_zbuffer while reading in data!\n");
  425.         printf ("(n=%d, nread=%ld)\n", n, nread);
  426.         exit (1);
  427.       }
  428.     
  429. #ifdef LIGHTSPEED
  430.     check_interrupt ();
  431. #endif
  432.   }
  433.  
  434.  
  435. /* function to return a pointer to the right place to store the next
  436.  * output item for the nth zbuffer ... when the buffer becomes full,
  437.  * it flushes it to disk, resets pointers, etc.
  438.  */
  439.  
  440. char *next_output_item (n)
  441.   int n;
  442.   {
  443.     char *result;
  444.     void flush_zbuffer();
  445.     
  446.     if (zbuffer[n].zbufcounter == zbuffer[n].zbufsize)
  447.         flush_zbuffer (n);
  448.     
  449.     result = zbuffer[n].zbufp;
  450.     zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  451.     zbuffer[n].zbufcounter += zbuffer[n].zbufitemsize;
  452.     return (result);
  453.   }
  454.  
  455.  
  456. /* function to flush out a zbuffer to the disk ... might as well give user
  457.  * a chance to interrupt here (in the Macintosh version), as long as we
  458.  * have to go to the disk anyway....
  459.  */
  460.  
  461. void flush_zbuffer (n)
  462.   int n;
  463.   {
  464.     long chars_written;
  465.     void exit();
  466.     
  467.     if (zbuffer[n].zbufcounter == 0)
  468.         return;
  469.  
  470. #ifdef LIGHTSPEED
  471.     chars_written = zbuffer[n].zbufcounter;
  472.     FSWrite (zbuffer[n].zbuffilep->refnum, &chars_written,
  473.                 zbuffer[n].zbufbase);
  474. #else
  475.     chars_written = fwrite (zbuffer[n].zbufbase, sizeof(char),
  476.                 (int)zbuffer[n].zbufcounter, zbuffer[n].zbuffilep);
  477. #endif
  478.     if (ferror(zbuffer[n].zbuffilep) || chars_written == 0)
  479.       {
  480.         printf ("\nFatal error in flush_zbuffer while writing out data!\n");
  481.         printf ("(n=%d, zbufcounter=%ld, chars_written=%ld)\n", n,
  482.                     zbuffer[n].zbufcounter, chars_written);
  483.         exit(1);
  484.       }
  485.     
  486.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  487.     zbuffer[n].zbufcounter = 0;
  488.  
  489. #ifdef LIGHTSPEED
  490.     check_interrupt ();
  491. #endif
  492.   }
  493.   
  494.  
  495. /* ---------------build_indices.c file---------------- */
  496.  
  497. /* file build_indices.c ... by ^z, 870820-0913-...
  498.  *
  499.  * revised 870930-871007 to allow more user options on keeping/discarding
  500.  *    punctuation, etc. -- ideas based on Bill Hole's suggestions
  501.  *
  502.  * contains subroutine to build indices for each chunk of input document
  503.  * (database) text file for program qndxr ... 
  504.  *
  505.  * Strategy is as outlined in qndxr:  take in a big chunk of the doc_file,
  506.  *    generate the pointers to each word in the buffer as the buffer contents
  507.  *    are converted into appropriate (all caps, delimiters filtered into
  508.  *    spaces) form for sorting; sort the pointers in memory; and then write
  509.  *    out to disk the pointers and keys in the ndxr.c format for *.k and *.p
  510.  *    files.
  511.  *
  512.  * Allocate space for the doc and ptr buffers here so as to maximize use
  513.  * of available memory ... note that we need to have room for the doc
  514.  * buffer, for a ptr buffer that might (in the worst case of a file full
  515.  * of 1-letter words) be twice as long as the doc buffer, and also space
  516.  * for two standard zbuffers to accumulate the output *.k and *.p file
  517.  * info in before sending it to disk.
  518.  *
  519.  * Note that for speed, while they are being sorted the pointers just point
  520.  *    directly to the key strings in the input buffer; they must be converted
  521.  *    into true offset pointers relative to the 0th byte of the document file
  522.  *    as they are written to disk in the *.p file!  Make sure that all of
  523.  *    the delimiters in the document/database buffer are converted into
  524.  *    '\0' characters so that string comparison functions will work right.
  525.  *
  526.  * Also note that to avoid edge effects at the end of the buffer, an extra
  527.  *    amount of space is required at the end of the buffer, of length
  528.  *    KEY_LENGTH, to accomodate the end of the last word in the buffer.
  529.  *
  530.  * Use static local variables in the function here to keep track of where
  531.  *    we are in the document file from one chunk to the next, what chunk
  532.  *    number we are on now, etc.
  533.  *
  534.  * Give the user a chance to interrupt operations (in the Macintosh
  535.  * version of this program) at intervals here, as long as
  536.  * there are time-consuming I/O or sorting or scanning operations
  537.  * to be done ...
  538.  */
  539.  
  540.  
  541. int build_indices ()
  542.   {
  543.     static int pass_number = 0;
  544.     long doc_bufsiz, offset, load_doc_buffer(), nwords, 
  545.             ftell();
  546.     extern long zbufsiz;
  547.     extern FILE *doc_file;
  548.     char *doc, **ptr, *malloc(), *mlalloc(), *calloc(), *clalloc();
  549.     void zqsort(), write_sorted_files();
  550.  
  551.     doc_bufsiz = 2 * NMERGE * zbufsiz / 3;
  552.     DEBUG ("--allocating doc buffer of size %ld\n", doc_bufsiz + KEY_LENGTH);
  553.     doc = make_buf (doc_bufsiz + KEY_LENGTH);
  554.     
  555.     DEBUG ("--allocating ptr buffer of size %ld\n", doc_bufsiz * 2);
  556.     ptr = (char **)make_buf (doc_bufsiz * 2);
  557.     
  558. #ifdef LIGHTSPEED
  559.     check_interrupt ();
  560. #endif
  561.  
  562.     offset = ftell (doc_file);    
  563.     DEBUG ("--loading doc buffer beginning at offset %ld\n", offset);    
  564.     nwords = load_doc_buffer (doc, doc_bufsiz, ptr);
  565.  
  566.     if (nwords == 0)
  567.       {
  568.         DEBUG ("--Building done ... now freeing doc & ptr buffers\n", NULL);
  569.         free (doc);
  570.         free ((char *)ptr);
  571.         return (FALSE);
  572.       }
  573.     
  574.     printf ("Index subfile #%d contains %ld words...\n", pass_number,
  575.                 nwords);
  576.     
  577. #ifdef LIGHTSPEED
  578.     check_interrupt ();
  579. #endif
  580.  
  581.     DEBUG ("--sorting ptr array\n", NULL);
  582.     zqsort (ptr, ptr + nwords);
  583.     
  584. #ifdef LIGHTSPEED
  585.     check_interrupt ();
  586. #endif
  587.  
  588.     DEBUG ("--writing sorted keys and ptrs to disk\n", NULL);
  589.     write_sorted_files (doc, ptr, nwords, pass_number, offset);
  590.     
  591. #ifdef LIGHTSPEED
  592.     check_interrupt ();
  593. #endif
  594.  
  595.     DEBUG ("--freeing doc & ptr buffers\n", NULL);
  596.     free (doc);
  597.     free ((char *)ptr);
  598.     
  599.     ++pass_number;
  600.     return (TRUE);
  601.   }
  602.  
  603.  
  604. /* ---------------doc_buf.c file------------------ */
  605.  
  606. /* file doc_buf.c ...  by ^z 870830-0919-...
  607.  * functions to load in text from the document file and then
  608.  * save out keys and pointers to the *.k and *.p files ...
  609.  * modified 871007-... to unify the doc-buffer loading with the
  610.  * character-filtering and the pointer array building....
  611.  */
  612.  
  613. /* function to create a buffer for me to use...
  614.  */
  615.  
  616. char *make_buf (bufsiz)
  617.   long bufsiz;
  618.   {
  619.     char *buf, *malloc(), *mlalloc();
  620.     void exit();
  621.     
  622.     DEBUG ("--allocating a buffer, size = %ld\n", bufsiz);
  623.     
  624. #ifdef LIGHTSPEED
  625.     buf = mlalloc (bufsiz);
  626. #else
  627.     buf = malloc ((unsigned int)bufsiz);
  628. #endif
  629.  
  630.     if (buf == NULL)
  631.       {
  632.         printf ("\nFatal error in attempt to allocate a buffer!\n");
  633.         printf ("(bufsiz=%ld)\n", bufsiz);
  634.         exit(1);
  635.       }
  636.     
  637.     return (buf);
  638.   }
  639.  
  640.  
  641. /* function to load the document buffer ... bring in doc_bufsiz
  642.  * characters, and then enough more to finish out the final word,
  643.  * followed by a terminal delimiter .... as the characters are read
  644.  * in, filter them appropriately (depending on user choices) and
  645.  * build the pointer array in memory to the first character of each
  646.  * word ... return the total number of words that were
  647.  * read in to the buffer (zero if we're finished with the file)
  648.  *
  649.  * ... note that one must be sure to pull in and throw away
  650.  * any excess characters beyond KEY_LENGTH in the final word, so that
  651.  * the remaining fragment doesn't show up as the first "word" in the
  652.  * next chunk of the file....
  653.  *
  654.  * Routine modified 871007-... in order to unify the buffer-loading and
  655.  * character-filtering and pointer-array-building operations, and to go
  656.  * back to using getc() from <stdio> rather than Macintosh-specific
  657.  * operations for loading the buffer....
  658.  */
  659.  
  660. long load_doc_buffer (doc, doc_bufsiz, ptr)
  661.   char *doc, **ptr;
  662.   long doc_bufsiz;
  663.   {
  664.     int c, i, in_a_word = FALSE;
  665.     char **ptr0, *end_doc_buf;
  666.     extern FILE *doc_file;
  667.  
  668.     DEBUG ("--Loading document buffer...\n", NULL);
  669.      
  670.      ptr0 = ptr;
  671.      end_doc_buf = doc + doc_bufsiz;
  672.      
  673.      while (doc < end_doc_buf)
  674.        {
  675.          c = filtered_getc ();
  676.          DEBUG ("--filtered character = \"%c\"\n", c);
  677.          if (c == EOF)
  678.            {
  679.              *doc++ = '\0';
  680.              in_a_word = FALSE;
  681.              break;
  682.            }
  683.          if (! c)
  684.              in_a_word = FALSE;
  685.          else if (! in_a_word)
  686.            {
  687.              *ptr++ = doc;
  688.              in_a_word = TRUE;
  689.              DEBUG ("--adding new ptr = %ld\n", doc);
  690.            }
  691.          *doc++ = c;
  692.        }
  693.      
  694.      if (doc == end_doc_buf && in_a_word)
  695.       {
  696.         DEBUG ("--finishing off a final buffer word...\n", NULL);
  697.         for (i = 0; i < KEY_LENGTH; ++i)
  698.          {
  699.            c = filtered_getc ();
  700.            if (c == EOF)
  701.              {
  702.                *doc++ = '\0';
  703.                break;
  704.              }
  705.            if (! c)
  706.              {
  707.                *doc++ = '\0';
  708.                break;
  709.              }
  710.            *doc++ = c;
  711.          }
  712.        if (i == KEY_LENGTH)
  713.            while (filtered_getc ())
  714.                 ;
  715.        }
  716.      
  717.      return (ptr - ptr0);
  718.   }
  719.  
  720.  
  721. /* function to get the next character from the document file and filter it
  722.  * as the user desires ... return:
  723.  *  EOF  if end of file encountered;
  724.  *  '/0' if the character is a delimiter;
  725.  *  otherwise, the character itself (filtered into upper-case,
  726.  *        if it was lower-case)
  727.  */
  728.  
  729. int filtered_getc ()
  730.   {
  731.     static int prevc, c = '\0';
  732.     int nextc;
  733.     extern int keep_all_punct, keep_embedded_punct, keep_special_chars;
  734.     extern FILE *doc_file;
  735.  
  736.     prevc = c;
  737.     c = getc (doc_file);
  738.     
  739.     if (c == EOF)
  740.         return (EOF);
  741.     
  742.     if (islower (c))
  743.         return (c = toupper (c));
  744.     
  745.     if (isupper (c) || isdigit (c))
  746.         return (c);
  747.     
  748.     if (isspace (c))
  749.         return (c = '\0');
  750.     
  751.     if (keep_special_chars && ! isascii (c))
  752.         return (c);
  753.     
  754.     if (keep_all_punct && ispunct (c))
  755.         return (c);
  756.     
  757.     if (keep_embedded_punct && ispunct (c))
  758.       {
  759.         if (prevc == '\0')
  760.             return (c = '\0');
  761.         nextc = getc (doc_file);
  762.         ungetc (nextc, doc_file);
  763.         if (nextc == EOF)
  764.             return (c = '\0');
  765.         if (isalnum (nextc) || (keep_special_chars && ! isascii (nextc)))
  766.             return (c);
  767.         else
  768.             return (c = '\0');
  769.       }
  770.     
  771.     return (c = '\0');
  772.   }
  773.  
  774. /* ------------------------file_utils.c------------- */
  775.  
  776. /* file file_utils.c ... by ^z -- 870820-0913-...
  777.  * some utility routines for qndxr project, associated with files...
  778.  */
  779.  
  780.  
  781. /* function to write out sorted k & p files based on the doc and ptr
  782.  * arrays in memory....
  783.  *
  784.  * The kfile format is as described in detail elsewhere:
  785.  *    the key word, turned into all capital letters and with spaces
  786.  *        afterward, of fixed length KEY_LENGTH; and
  787.  *    the cumulative count of how many words have passed before, including
  788.  *        the current word, a long integer.
  789.  *
  790.  * Function revised 870907-... by ^z to use zbuffer method....
  791.  */
  792.  
  793. void write_sorted_files (doc, ptr, nwords, pass_number, offset)
  794.   char *doc, **ptr;
  795.   long nwords, offset;
  796.   int pass_number;
  797.   {
  798.     extern long zbufsiz;
  799.     FILE *kfile, *pfile, *open_kfile(), *open_pfile();
  800.     char *prev_word, *next_output_item();
  801.     KEY_REC *outk;
  802.     long *outp, i, file_size ();
  803.     void create_zbuffer(), write_new_key();
  804.     
  805.     DEBUG ("--Entering write_sorted_files with nwords %ld\n", nwords);
  806.     if (nwords == 0)
  807.         return;
  808.     
  809.     DEBUG ("--Opening kfile & pfile for pass_number = %d\n", pass_number);
  810.     kfile = open_kfile (pass_number);
  811.     pfile = open_pfile (pass_number);
  812.     
  813.     DEBUG ("--Creating buffers for keys & ptrs, size = %ld\n", zbufsiz);
  814.     create_zbuffer (0, zbufsiz, kfile, sizeof(KEY_REC));
  815.     create_zbuffer (1, zbufsiz, pfile, sizeof(long));
  816.  
  817.     DEBUG ("--Beginning to write keys and ptrs; first key=%.28s\n", ptr[0]);
  818.     prev_word = ptr[0];
  819.     outk = (KEY_REC *)next_output_item (0);
  820.     write_new_key (ptr[0], outk->kkey);
  821.     
  822.     for (i = 0; i < nwords; ++i)
  823.       {
  824.         if (is_new_word (prev_word, ptr[i]))
  825.           {
  826.             outk->ccount = i;
  827.             outk = (KEY_REC *)next_output_item (0);
  828.             write_new_key (ptr[i], outk->kkey);
  829.             prev_word = ptr[i];
  830.           }
  831.         outp = (long *)next_output_item (1);
  832.         *outp = (ptr[i] - doc) + offset;
  833.       }
  834.     outk->ccount = i;
  835.  
  836.     flush_zbuffer (0);
  837.     flush_zbuffer (1);
  838.     
  839.     DEBUG ("--Getting rid of key and ptr buffers...\n", NULL);
  840.     free_zbuffer (0);
  841.     free_zbuffer (1);
  842.     
  843.     printf (" ...%ld distinct words\n",
  844.             file_size (kfile) / sizeof(KEY_REC));
  845.     fclose (kfile);
  846.     fclose (pfile);
  847.   }
  848.  
  849.  
  850. /* function to determine if the current word is the same as or different
  851.  * from the previous word -- if it is different, we'll need to write an
  852.  * entry out to the key file kfile -- compare the words up to the first
  853.  * '\0', or for a maximum distance of KEY_LENGTH, and return TRUE
  854.  * if they differ, FALSE if they are identical that far.  Thus, a simple
  855.  * call to zstrcmp() does the job.... but keep ours as a function instead
  856.  * of a macro call for the moment, for safety and readability....
  857.  */
  858.  
  859. int is_new_word (w0, w1)
  860.   char *w0, *w1;
  861.   {
  862.     return (zstrcmp (w0, w1));
  863.   }
  864.  
  865.  
  866. /* function to write out a new key entry in the key_file:
  867.  * KEY_LENGTH letters consisting of the key word (which will be found
  868.  * delimited by a '\0'), followed by enough blanks to fill out the
  869.  * record to total length KEY_LENGTH ...
  870.  */
  871.  
  872. void write_new_key (p, kp)
  873.   register char *p, *kp;
  874.   {
  875.     register int i, c;
  876.     
  877.     for (i = 0; i < KEY_LENGTH; ++i)
  878.       {
  879.         c = *p++;
  880.         if (c == '\0')
  881.             break;
  882.         *kp++ = c;
  883.       }
  884.  
  885.     for ( ; i < KEY_LENGTH; ++i)
  886.         *kp++ = ' ';
  887.   }
  888.  
  889.  
  890.  
  891. /* ---------------------merge_files.c--------------- */
  892.  
  893. /* file merge_files.c ...  870902-... ^z
  894.  * more functions to do the work of merging subindices together ...
  895.  * with buffering of inputs and outputs ...
  896.  */
  897.  
  898.  
  899. /* function to do the real work of merging sorted k & p
  900.  * files into a single sorted file...
  901.  *
  902.  * Procedure is as follows:
  903.  *
  904.  *    Compare the current key records from each of the N files to be merged.
  905.  *    Take the smallest of the keys (or, if there is a tie, take the one
  906.  *    from the earlier file number) and write its pointer records out to
  907.  *    the *.p file for the next generation.  If the key is a new one, that
  908.  *    is, if it differs from the previous key, write out the previous key
  909.  *    word and the value for cumulative_counts to the *.k file, and reset
  910.  *    the previous key's value to that of the current key.  Then repeat
  911.  *    this whole procedure, until all the input files are exhausted.
  912.  *
  913.  *    The above works provided that we are careful in choosing the smallest
  914.  *    key and never let a file that has been exhausted (reached EOF) win a
  915.  *    comparison.  The function smallest_key does that properly below, since
  916.  *    a file that is at EOF has returned a NULL pointer for its key_rec...
  917.  *
  918.  *  For each file, the variable prev_cc[i] holds the previous value of
  919.  *    cumulative_counts for that file, so that we can determine how
  920.  *    many ptr_recs to write out by doing a simple subtraction.
  921.  *
  922.  * Buffer numbering scheme:  the Kth input file has zbuffer #K
  923.  *    for its keys and zbuffer #(K+n) for its pointers; the output
  924.  *    buffers are zbuffers #(2*n) for keys and #(2*n+1) for pointers.
  925.  */
  926.  
  927. void nway_merge_kpfiles (ink, inp, outk, outp, n)
  928.   FILE *ink[], *inp[], *outk, *outp;
  929.   register int n;
  930.   {
  931.     register int i;
  932.     KEY_REC *kr[NMERGE], prev_key;
  933.     long prev_cc[NMERGE], out_cc;
  934.     extern long zbufsiz;
  935.     char *strncpy();
  936.     void copy_ptr_recs(), copy_key_rec();
  937.     
  938.     DEBUG ("--entering nway_merge_kpfiles with n=%d\n", n);
  939.     for (i = 0; i < n; ++i)
  940.         prev_cc[i] = 0;
  941.     out_cc = 0;
  942.     
  943.     for (i = 0; i < n; ++i)
  944.       {
  945.         create_zbuffer (i, zbufsiz, ink[i], sizeof(KEY_REC));
  946.         create_zbuffer (i + n, zbufsiz, inp[i], sizeof(long));
  947.       }
  948.     create_zbuffer (2 * n, zbufsiz, outk, sizeof(KEY_REC));
  949.     create_zbuffer (2 * n + 1, zbufsiz, outp, sizeof(long));
  950.     
  951.     for (i = 0; i < n; ++i)
  952.         kr[i] = (KEY_REC *)next_input_item (i);
  953.     
  954.     i = smallest_key (kr, n);
  955.     strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  956.     DEBUG ("--first key is %.28s\n", prev_key.kkey);
  957.  
  958.     while (merge_not_finished (kr, n))
  959.       {
  960.         i = smallest_key (kr, n);
  961.         if (zstrcmp (prev_key.kkey, kr[i]->kkey))
  962.           {
  963.             copy_key_rec (prev_key.kkey, out_cc, 2 * n);
  964.             strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  965.           }
  966.         copy_ptr_recs (i + n, kr[i]->ccount - prev_cc[i], 2 * n + 1);
  967.         out_cc += kr[i]->ccount - prev_cc[i];
  968.         prev_cc[i] = kr[i]->ccount;
  969.         kr[i] = (KEY_REC *)next_input_item (i);
  970.       }
  971.     
  972.     copy_key_rec (prev_key.kkey, out_cc, 2 * n);
  973.     DEBUG ("--finished nway merge ... final key=%.28s\n", prev_key.kkey);
  974.     flush_zbuffer (2 * n);
  975.     flush_zbuffer (2 * n + 1);
  976.     for (i = 0; i < 2 * n + 2; ++i)
  977.         free_zbuffer (i);
  978.   }
  979.  
  980.  
  981. /* function to copy a chosen number of ptr_recs (longs) from one file
  982.  * to another ... used in merging two files by merge_kpfiles() above....
  983.  * revised and simplified to use zbuffers....870902 ... ^z
  984.  */
  985.  
  986. void copy_ptr_recs (inzbuf, count, outzbuf)
  987.   register int inzbuf, outzbuf;
  988.   register long count;
  989.   {
  990.     register long *inp, *outp;
  991.     char *next_input_item(), *next_output_item();
  992.  
  993.     for ( ; count > 0; --count)
  994.       {
  995.         inp = (long *)next_input_item (inzbuf);
  996.         outp = (long *)next_output_item (outzbuf);
  997.         *outp = *inp;
  998.       }
  999.   }
  1000.  
  1001.  
  1002. /* function to write a key record including kkey (key word) and ccount
  1003.  * (cumulative_count) to an output file...
  1004.  */
  1005.  
  1006. void copy_key_rec (kkey, cc, outzbuf)
  1007.   char *kkey;
  1008.   long cc;
  1009.   int outzbuf;
  1010.   {
  1011.     KEY_REC *outp;
  1012.     char *strncpy(), *next_output_item();
  1013.  
  1014.     outp = (KEY_REC *)next_output_item (outzbuf);
  1015.     strncpy (outp->kkey, kkey, KEY_LENGTH);
  1016.     outp->ccount = cc;
  1017.   }
  1018.  
  1019.  
  1020. /* simple function to see if we are not yet finished with all of the input
  1021.  * files coming in to the merge operation ... signified by at least one of
  1022.  * the key pointers being non-NULL....
  1023.  */
  1024.  
  1025. int merge_not_finished (kr, n)
  1026.   KEY_REC *kr[];
  1027.   register int n;
  1028.   {
  1029.     register int i;
  1030.     
  1031.     for (i = 0; i < n; ++i)
  1032.         if (kr[i] != NULL)
  1033.             return (TRUE);
  1034.     
  1035.     return (FALSE);
  1036.   }
  1037.  
  1038.  
  1039. /* function to determine the smallest of the n keys pointed to by the
  1040.  * kr[] vector of pointers to KEY_RECs ... note that a NULL ptr ranks
  1041.  * after any other...also note that in case of a tie, the smaller
  1042.  * value of i is the one to return (for a stable merging sort)
  1043.  */
  1044.  
  1045. smallest_key (kr, n)
  1046.   KEY_REC *kr[];
  1047.   register int n;
  1048.   {
  1049.     register int i, smallest;
  1050.  
  1051.     for (i = 0; i < n; ++i)
  1052.         if (kr[i] != NULL)
  1053.           {
  1054.             smallest = i;
  1055.             break;
  1056.           }
  1057.  
  1058.     for (i = smallest + 1; i < n; ++i)
  1059.         if (kr[i] != NULL)
  1060.             if (zstrcmp (kr[smallest]->kkey, kr[i]->kkey) > 0)
  1061.                 smallest = i;
  1062.  
  1063.     return (smallest);
  1064.   }
  1065.  
  1066.  
  1067. /* -------------------------merge_indices.c-------------- */
  1068.  
  1069. /* file "merge_indices.c" ... by ^z -- 870823-...
  1070.  * function to merge sorted indices together repeatedly until finished
  1071.  * with them all in a single set of *.k/*.p files ...
  1072.  *
  1073.  * The merging strategy is straightforward enough:
  1074.  *    Let "g" denote the generation_number and "f" denote the file_number.
  1075.  *    Temporary file names begin with the letter x, which is then followed
  1076.  *    by a generation number (decimal), the letter k or p (standing for
  1077.  *    key or ptr, respectively), and then the file number (decimal).  Thus,
  1078.  *    the file "x0k0" is the keys file #0 for generation #0 (the starting,
  1079.  *    pre-merging, generation), file "x2p3" is the ptr file #3 for generation
  1080.  *    #2, etc.
  1081.  *
  1082.  * (The following discussion is specifically for a 2-way merge ... but
  1083.  * the generalization for N-way merging is straightforward.)
  1084.  *
  1085.  *    On a given call to merge_indices, the following may happen:
  1086.  *        - files xgkf/xgpf and xgk(f+1)/xgp(f+1) are merged into files
  1087.  *            x(g+1)k(f/2)/x(g+1)p(f/2), and then the parent files are
  1088.  *            deleted;
  1089.  *        - file xgkf isn't found, which means we are done with this
  1090.  *            generation and must go on to the next;
  1091.  *        - file xgk(f+1) isn't found, which means that either we are
  1092.  *            completely done with the merging work (if f=0) and just
  1093.  *            have to rename the files xgkf/xgpf into the correct final
  1094.  *            names (that is, doc_filename.k/doc_filename.p), or else
  1095.  *            (if f>0) we have an odd number of files for this level
  1096.  *            of merging, and therefore just have to rename xgkf/xgpf
  1097.  *            to x(g+1)k(f/2)/x(g+1)p(f/2).
  1098.  */
  1099.  
  1100.  
  1101. int merge_indices (doc_filename)
  1102.   char *doc_filename;
  1103.   {
  1104.     static int generation_number = 0, file_number = 0;
  1105.     FILE *ink[NMERGE], *inp[NMERGE], *outk, *outp, *open_inkfile(),
  1106.             *open_inpfile(), *open_outkfile(), *open_outpfile();
  1107.     void fix_oddball_file_name(), fix_final_file_names(), merge_kpfiles(),
  1108.             remove_used_infiles(), close_infiles();
  1109.     long inwords, indistinctwords, outdistinctwords, file_size();
  1110.     int i, n;
  1111.     
  1112.     for (n = 0; n < NMERGE; ++n)
  1113.       {
  1114.         ink[n] = open_inkfile (generation_number, file_number + n);
  1115.         if (ink[n] == NULL)
  1116.             break;
  1117.         inp[n] = open_inpfile (generation_number, file_number + n);
  1118.       }
  1119.     
  1120.     if (file_number + n == 1)
  1121.       {
  1122.         DEBUG ("--All finished with merging files!\n", NULL);
  1123.         printf ("\nFinished with index sorting!  Final file sizes:\n");
  1124.         printf ("%9ld bytes of distinct key words\n", file_size (ink[0]));
  1125.         printf ("%9ld bytes of pointers to words\n", file_size (inp[0]));
  1126.         close_infiles (ink, inp, n);
  1127.         fix_final_file_names (generation_number, doc_filename);
  1128.         return (FALSE);
  1129.       }
  1130.     
  1131.     if (n < 2)
  1132.       {
  1133.         DEBUG ("--finished generation_number=%d ", generation_number);
  1134.         DEBUG ("-- file_number=%d\n", file_number);
  1135.         if (n == 1)
  1136.           {
  1137.             close_infiles (ink, inp, n);
  1138.             fix_oddball_file_name (generation_number, file_number);
  1139.           }
  1140.         ++generation_number;
  1141.         file_number = 0;
  1142.         return (TRUE);
  1143.       }
  1144.     
  1145.     outk = open_outkfile (generation_number, file_number);
  1146.     outp = open_outpfile (generation_number, file_number);
  1147.     
  1148.     inwords = 0;
  1149.     indistinctwords = 0;
  1150.     for (i = 0; i < n; ++i)
  1151.       {
  1152.         inwords += file_size (inp[i]) / sizeof(long);
  1153.         indistinctwords += file_size (ink[i]) / sizeof(KEY_REC);
  1154.       }
  1155.     printf ("Merge pass #%d.%d\n", generation_number, file_number / NMERGE);
  1156.     printf ("Input files contain %ld words -- %ld distinct words...\n",
  1157.                 inwords, indistinctwords);
  1158.  
  1159.     nway_merge_kpfiles (ink, inp, outk, outp, n);
  1160.     
  1161.     outdistinctwords = file_size (outk) / sizeof(KEY_REC);
  1162.     printf (" ... merged result has %ld distinct words.\n",
  1163.                 outdistinctwords);
  1164.     
  1165.     close_infiles (ink, inp, n);
  1166.     fclose (outk);
  1167.     fclose (outp);
  1168.     remove_used_infiles (generation_number, file_number, n);
  1169.     
  1170.     file_number += NMERGE;
  1171.     
  1172.     return (TRUE);
  1173.   }
  1174.  
  1175. /* --------------------merge_utils.c---------------- */
  1176.  
  1177. /* file "merge_utils.c" ... 870902-... ^z
  1178.  * misc. utilities for the merge_indices functions...
  1179.  */
  1180.  
  1181.  
  1182. /* function to open an input key file for this generation and file number
  1183.  */
  1184.  
  1185. FILE *open_inkfile (generation_number, file_number)
  1186.   int generation_number, file_number;
  1187.   {
  1188.     FILE *fopen();
  1189.     char fname[32];
  1190.     
  1191.     sprintf (fname, "x%dk%d", generation_number, file_number);
  1192.     return (fopen (fname, "rb"));
  1193.   }
  1194.  
  1195.  
  1196. /* function to open an input ptr file for this generation and file number
  1197.  */
  1198.  
  1199. FILE *open_inpfile (generation_number, file_number)
  1200.   int generation_number, file_number;
  1201.   {
  1202.     FILE *fopen();
  1203.     char fname[32];
  1204.     
  1205.     sprintf (fname, "x%dp%d", generation_number, file_number);
  1206.     return (fopen (fname, "rb"));
  1207.   }
  1208.  
  1209.  
  1210. /* function to open an output key file for this generation and file number
  1211.  */
  1212.  
  1213. FILE *open_outkfile (generation_number, file_number)
  1214.   int generation_number, file_number;
  1215.   {
  1216.     FILE *fopen();
  1217.     char fname[32];
  1218.     
  1219.     sprintf (fname, "x%dk%d", generation_number + 1, file_number / NMERGE);
  1220.     return (fopen (fname, "wb"));
  1221.   }
  1222.  
  1223.  
  1224. /* function to open an output ptr file for this generation and file number
  1225.  */
  1226.  
  1227. FILE *open_outpfile (generation_number, file_number)
  1228.   int generation_number, file_number;
  1229.   {
  1230.     FILE *fopen();
  1231.     char fname[32];
  1232.     
  1233.     sprintf (fname, "x%dp%d", generation_number + 1, file_number / NMERGE);
  1234.     return (fopen (fname, "wb"));
  1235.   }
  1236.  
  1237.  
  1238. /* function to rename the remaining last unpaired key file & ptr file
  1239.  * from one generation to the next...
  1240.  */
  1241.  
  1242. void fix_oddball_file_name (generation_number, file_number)
  1243.   int generation_number, file_number;
  1244.   {
  1245.     char oldname[32], newname[32];
  1246.     
  1247.     sprintf (oldname, "x%dk%d", generation_number, file_number);
  1248.     sprintf (newname, "x%dk%d", generation_number + 1, file_number / NMERGE);
  1249.     if (rename (oldname, newname))
  1250.         printf ("Sorry -- error in attempt to rename %s to %s!\n", oldname,
  1251.                 newname);
  1252.     
  1253.     sprintf (oldname, "x%dp%d", generation_number, file_number);
  1254.     sprintf (newname, "x%dp%d", generation_number + 1, file_number / NMERGE);
  1255.     if (rename (oldname, newname))
  1256.         printf ("Sorry -- error in attempt to rename %s to %s!\n", oldname,
  1257.                 newname);
  1258.   }
  1259.  
  1260.  
  1261. /* function to give the final key and ptr files their proper ultimate
  1262.  * names ...
  1263.  */
  1264.  
  1265. void fix_final_file_names (generation_number, doc_filename)
  1266.   int generation_number;
  1267.   char *doc_filename;
  1268.   {
  1269.     char oldname[32], finalname[65];
  1270.     
  1271.     sprintf (oldname, "x%dk0", generation_number);
  1272.     sprintf (finalname, "%s.k", doc_filename);
  1273.     if (rename (oldname, finalname))
  1274.         printf ("Sorry -- error in renaming file %s to %s!\n", oldname,
  1275.                 finalname);
  1276.  
  1277.     sprintf (oldname, "x%dp0", generation_number);
  1278.     sprintf (finalname, "%s.p", doc_filename);
  1279.     if (rename (oldname, finalname))
  1280.         printf ("Sorry -- error in renaming file %s to %s!\n", oldname,
  1281.                 finalname);
  1282.   }
  1283.  
  1284.  
  1285. /* function to get rid of the superfluous k & p files now that they
  1286.  * have been merged into the next generation....
  1287.  */
  1288.  
  1289. void remove_used_infiles (generation_number, file_number, n)
  1290.   int generation_number, file_number, n;
  1291.   {
  1292.     char fname[32];
  1293.     register int i;
  1294.     
  1295.     for (i = 0; i < n; ++i)
  1296.       {
  1297.         sprintf (fname, "x%dk%d", generation_number, file_number + i);
  1298.         DEBUG ("--removing %s\n", fname);
  1299.         if (unlink (fname))
  1300.             printf ("Sorry -- unable to delete file %s!\n", fname);
  1301.         sprintf (fname, "x%dp%d", generation_number, file_number + i);
  1302.         DEBUG ("--removing %s\n", fname);
  1303.         if (unlink (fname))
  1304.             printf ("Sorry -- unable to delete file %s!\n", fname);
  1305.       }
  1306.   }
  1307.  
  1308.  
  1309. /* function to close out the ink and inp files that have been opened...
  1310.  */
  1311.  
  1312. void close_infiles (ink, inp, n)
  1313.   FILE *ink[], *inp[];
  1314.   register int n;
  1315.   {
  1316.     register int i;
  1317.     
  1318.     for (i = 0; i < n; ++i)
  1319.       {
  1320.         fclose (ink[i]);
  1321.         fclose (inp[i]);
  1322.       }
  1323.   }
  1324.  
  1325.  
  1326. /* ---------------------misc_utils.c----------------- */
  1327.  
  1328. /* file "misc_utils.c" -- miscellaneous utilities for the qndxr project...
  1329.  * by ^z -- 870821-...
  1330.  */
  1331.  
  1332.  
  1333. /* this function returns a value for the size of the internal buffers,
  1334.  * zbufsiz, and it also takes care of setting the other global parameters,
  1335.  * keep_all_punct, keep_embedded_punct, and keep_special_chars,
  1336.  * which govern how punctuation and special characters are handled.
  1337.  * They are set based on flags such as -e, -a, and -s in the input line.
  1338.  * The input parameters are taken one after another, and any that do
  1339.  * not convert to a nonzero number are scanned for the letters "e", "a", and
  1340.  * "s".  If a parameter is not reset, the default is to leave keep_all_punct,
  1341.  * keep_embedded_punct, and keep_special_chars as FALSE.
  1342.  * The default memory size is DEFAULT_MEMSIZ, set in the header file.
  1343.  */
  1344.  
  1345. long set_params (argc, argv)
  1346.   int argc;
  1347.   char *argv[];
  1348.   {
  1349.     int i;
  1350.     void set_parser_options();
  1351.     long zb = 0, n, atol(), set_zbufsiz();
  1352.     
  1353.     for (i = 2; i < argc; ++i)
  1354.       {
  1355.         n = atol (argv[i]);
  1356.         if (n != 0)
  1357.             zb = set_zbufsiz (n);
  1358.         else
  1359.             set_parser_options (argv[i]);
  1360.       }
  1361.     
  1362.     if (zb == 0)
  1363.         zb = set_zbufsiz (DEFAULT_MEMSIZ);
  1364.  
  1365.     return (zb);
  1366.   }
  1367.  
  1368.  
  1369.  
  1370. /* determine how big we should make the big buffers -- want to be sure
  1371.  * to have room for at least 2*NMERGE+2 of them at one time in memory,
  1372.  * so that the N-way merge function can hold all the input files
  1373.  * (2N) plus the output files (2).
  1374.  *
  1375.  * NOTE that the chosen buffer size must be a multiple of both sizeof(long)
  1376.  * and sizeof(KEY_REC); I ensure that very simply in what follows by
  1377.  * a little modular arithmetic.  I also take care of the sign and of the
  1378.  * requirement that the buffer size be non-zero -- thus, UNIX aficionados
  1379.  * can precede the parameter with a "-" with no ill effects.  I have put in
  1380.  * various safeguards against picking illegal buffer sizes, along with an
  1381.  * ultimate safety net small minimum value for zbufsiz.
  1382.  */
  1383.  
  1384. long set_zbufsiz (zb)
  1385.   long zb;
  1386.   {
  1387.     char *testb;
  1388.  
  1389.     if (zb < 0)
  1390.         zb = -zb;
  1391.     
  1392.     zb /=  (2 * NMERGE + 2);
  1393.     zb = zb - zb % (sizeof(KEY_REC) * sizeof(long));
  1394.     
  1395.     if (zb < sizeof(KEY_REC) * sizeof(long))
  1396.         zb = sizeof(KEY_REC) * sizeof(long);
  1397.  
  1398.     DEBUG ("--Checking for memory to support buffer size zb=%ld\n", zb);
  1399.     testb = make_buf ((2 * NMERGE + 2) * zb);
  1400.     free (testb);
  1401.     
  1402.     return (zb);
  1403.   }
  1404.  
  1405.  
  1406. /* function to set the parser options based on a character string ...
  1407.  * 'a' turns on keep_all_punct, 'e' turns on keep_embedded_punct,
  1408.  * and 's' turns on keep_special_chars
  1409.  */
  1410.  
  1411. void set_parser_options (str)
  1412.   char *str;
  1413.   {
  1414.     extern int keep_all_punct, keep_embedded_punct, keep_special_chars;
  1415.  
  1416.     while (*str)
  1417.       {
  1418.         if (*str == 'a')
  1419.           {
  1420.             keep_all_punct = TRUE;
  1421.             printf ("All punctuation characters will be kept.\n");
  1422.           }
  1423.         else if (*str == 'e')
  1424.           {
  1425.             keep_embedded_punct = TRUE;
  1426.             printf ("Embedded punctuation characters will be kept.\n");
  1427.           }
  1428.         else if (*str == 's')
  1429.           {
  1430.             keep_special_chars = TRUE;
  1431.             printf ("Special characters will be kept.\n");
  1432.           }
  1433.         
  1434.         ++str;
  1435.       }
  1436.   }
  1437.   
  1438.  
  1439.  
  1440. /* function to check for user interruption of operations (for use in the
  1441.  * Macintosh version of this program only) ... call SystemTask() to give
  1442.  * desk accessories a bit of time, and then check for non-null events
  1443.  * with GetNextEvent() ... if something comes along (a mouse click, or key
  1444.  * press, or whatever) let the user choose to exit the program or to
  1445.  * carry on ....
  1446.  */
  1447.  
  1448. #ifdef LIGHTSPEED
  1449.  
  1450. void check_interrupt ()
  1451.   {
  1452.     EventRecord myEvent;
  1453.     char cmd[256], *gets();
  1454.     void exit();
  1455.  
  1456.     SystemTask ();
  1457.     if (GetNextEvent (everyEvent, &myEvent))
  1458.       {
  1459.         fprintf (stderr, "\Quit indexing now?\n");
  1460.         gets (cmd);
  1461.         if (cmd[0] == 'y' || cmd[0] == 'Y')
  1462.             exit (0);
  1463.       }
  1464.   }
  1465.  
  1466. #endif
  1467.  
  1468.  
  1469. /* a very simple function to return the size of a file ... leave the file
  1470.  * pointer positioned at wherever it was when the routine was entered....
  1471.  * should work fine with stdio methods, but not guaranteed compatible when
  1472.  * mixed in with Mac-specific FSRead() function!
  1473.  */
  1474.  
  1475. long file_size (fp)
  1476.   FILE *fp;
  1477.   {
  1478.     long fpos, result, ftell();
  1479.     
  1480.     DEBUG ("--finding the size of file fp=%ld\n", fp);
  1481.     fpos = ftell (fp);
  1482.     fseek (fp, 0L, 2);
  1483.     result = ftell (fp);
  1484.     fseek (fp, fpos, 0);
  1485.     return (result);
  1486.   }
  1487.  
  1488.  
  1489. /* ----------------------open_files.c----------------- */
  1490.  
  1491. /* functions to open files as needed in qndxr work...
  1492.  */
  1493.  
  1494. FILE *open_docfile (argc, argv) 
  1495.   int argc;
  1496.   char *argv[];
  1497.   {
  1498.     FILE *fp, *fopen();
  1499.     void exit();
  1500.     
  1501.     if (argc < 2)
  1502.       {
  1503.         printf ("\nToo few command line arguments!\n");
  1504.         printf ("\nEnter a text file name (no embedded spaces allowed)\n");
  1505.         printf ("and the program will build and sort a complete inverted\n");
  1506.         printf ("index to that file.  Use \">\" in front of a file name to\n");
  1507.         printf ("redirect console output (UNIX-fashion) if desired.\n");
  1508.         printf ("Give the program a value for available memory (in bytes)\n");
  1509.         printf ("if the default value of 512kB is unsatisfactory ... larger\n");
  1510.         printf ("memory allows for faster index building and sorting.\n");
  1511.         printf ("Other command-line arguments:\n");
  1512.         printf ("  \"-e\" preserves embedded punctuation\n");
  1513.         printf ("  \"-a\" preserves all punctuation characters\n");
  1514.         printf ("  \"-s\" preserves special (non-ASCII) characters\n");
  1515.         printf ("\nContact Mark Zimmermann, 9511 Gwyndale Drive, Silver Spring\n");
  1516.         printf ("Maryland  20910  USA; 301-565-2166; science (at) nems.arpa;\n");
  1517.         printf ("[75066,2044] on CompuServe for further information. - ^z\n");
  1518.         exit (1);
  1519.       }
  1520.  
  1521.     if ((fp = fopen (argv[1], "r")) == NULL)
  1522.       {
  1523.         printf ("\nFatal error opening document file\"%s\"!\n", argv[1]);
  1524.         exit (1);
  1525.       }
  1526.     
  1527.     return (fp);
  1528.   }
  1529.  
  1530.  
  1531. /* open the key file with proper name for this pass ... file will be
  1532.  * named "x0kN" where N represents the pass number ....
  1533.  */
  1534.  
  1535. FILE *open_kfile (pass_number)
  1536.   int pass_number;
  1537.   {
  1538.     FILE *fopen();
  1539.     char fname[32];
  1540.     
  1541.     sprintf (fname, "x0k%d", pass_number);
  1542.     return (fopen (fname, "wb"));
  1543.   }
  1544.  
  1545.  
  1546. /* open the ptr file with proper name for this pass ... file will be
  1547.  * named "x0pN" where N represents the pass number ....
  1548.  */
  1549.  
  1550. FILE *open_pfile (pass_number)
  1551.   int pass_number;
  1552.   {
  1553.     FILE *fopen();
  1554.     char fname[32];
  1555.     
  1556.     sprintf (fname, "x0p%d", pass_number);
  1557.     return (fopen (fname, "wb"));
  1558.   }
  1559.  
  1560.  
  1561. /* ----------------------zqsort.c-------------------- */
  1562.  
  1563. /* file zqsort.c -- by ^z, 870823-...
  1564.  * my quicksort to sort out the ptr array ... based, at least initially,
  1565.  * on the Lightspeed C library qsort routine, specialized to the task
  1566.  * at hand here ...
  1567.  */
  1568.  
  1569.  
  1570. /*  sort elements "first" through "last" */
  1571.  
  1572. void zqsort (first, last)
  1573.   register char **first, **last;
  1574.   {
  1575.     register char **i, **j, *tmp;
  1576.  
  1577.     while (last - first > 1)
  1578.       {
  1579.         i = first;
  1580.         j = last;
  1581.         for (;;)
  1582.           {
  1583.             while (++i < last && compare_ptrs (i, first) < 0)
  1584.                 ;
  1585.             while (--j > first && compare_ptrs (j, first) > 0)
  1586.                 ;
  1587.             if (i >= j)
  1588.                  break;
  1589.              tmp = *i;
  1590.              *i = *j;
  1591.              *j = tmp;
  1592.           }
  1593.         tmp = *first;
  1594.         *first = *j;
  1595.         *j = tmp;
  1596.         if (j - first < last - (j + 1))
  1597.           {
  1598.             zqsort (first, j);
  1599.             first = j + 1;
  1600.           }
  1601.         else
  1602.           {
  1603.             zqsort (j + 1, last);
  1604.             last = j;
  1605.           }
  1606.       }
  1607.   }
  1608.  
  1609.  
  1610. /* function to compare two index ptrs and give a result appropriate
  1611.  * for quicksort to use in alphabetizing them....
  1612.  *
  1613.  * Since the words pointed to have already been turned into all capital
  1614.  * letters and delimiters have been filtered out, simply doing zstrcmp()
  1615.  * for KEY_LENGTH letters works fine!
  1616.  *
  1617.  * Slight modification to make the quicksort stable:  if two words tie,
  1618.  * then we want to compare their pointers to make the lesser one come
  1619.  * out first in the sort ...
  1620.  */
  1621.  
  1622. int compare_ptrs (p1, p2)
  1623.   register char **p1, **p2;
  1624.   {
  1625.     register int diff;
  1626.     
  1627.     diff = zstrcmp (*p1, *p2);
  1628.     if (diff == 0)
  1629.         diff = ((*p1 - *p2) > 0) ? 1 : -1;
  1630.     return (diff);
  1631.   }
  1632.  
  1633.  
  1634.  
  1635. /* my function to compare two strings and give a result as to who is
  1636.  * alphabetically earlier.  Note that this is almost the same as strncmp()
  1637.  * with the fixed value of KEY_LENGTH as the maximum comparison distance,
  1638.  * except that I must be sure to mask the characters to make them positive
  1639.  * (since we want to be able to handle the non-ASCII funny letters in
  1640.  * the Apple character set properly/consistently).  If the masking isn't
  1641.  * done, then inconsistent results can occur with those non-ASCII chars!
  1642.  */
  1643.  
  1644. int zstrcmp (s1, s2)
  1645.   register char *s1, *s2;
  1646.   {
  1647.     register int n = KEY_LENGTH;
  1648.     
  1649.     for (; --n && ((*s1 & CMASK) == (*s2 & CMASK)); s1++, s2++)
  1650.         if (!*s1) break;
  1651.         
  1652.     return ((*s1 & CMASK) - (*s2 & CMASK));
  1653.   }
  1654.  
  1655.